package Datastruct.Hufffman;

import java.util.*;

//测试哈夫曼树
public class HuffmanTree {
    public static void main(String[] args) {

        int[] array = {13, 7, 8, 29, 6, 1};
        Node root = createHuffmanTree(array);
        preOrder(root);

    }

    /**
     * 将数列转换为哈夫曼树
     */
    public static Node createHuffmanTree(int[] arrays) {
        /**
         * 1.遍历数组
         * 2.将每一个元素构成一个结点Node
         * 3.将node放入到一个集合当中并且已经是排序的，从小到大
         *
         * */
        List<Node> nodes = new ArrayList<Node>();
        //将元素转为node对象
        for (int i : arrays) {
            nodes.add(new Node(i));
        }

        /**
         * 1.排序 从小到大
         * 2. 取出最小的两个数  从集合   inde:0  index：1
         * Node   root==new Node(index:0+index:1)
         * root.left=index:0;
         * root.right=index:1;
         *
         * node.remove(index:0)
         *node.remove(index:1)
         * node.add(newRoot)
         * */

        while (nodes.size() > 1) {
            //先排序  从小到大
            Collections.sort(nodes);

            System.out.println("集合中的元素：" + nodes);

            Node leftnode = nodes.get(0);
            Node rightnode = nodes.get(1);

            //创建新的结点
            Node newroot = new Node(leftnode.value + rightnode.value);
            newroot.left = leftnode;
            newroot.right = rightnode;

            //从集合中删除取出来的两个结点
            nodes.remove(leftnode);
            nodes.remove(rightnode);

            //将新的结点添加到集合
            nodes.add(newroot);
        }

        //返回根节点
        return nodes.get(0);

    }

    //前序遍历
    public static void preOrder(Node root) {
        if (root != null) {
            root.preOrder();
        } else {
            System.out.println("空数，无数据。。。。。");
        }
    }

    //中序遍历

    public static void inOrder(Node root) {
        if (root != null) {
            root.inOrder();
        } else {
            System.out.println("空数，无数据。。。");
        }
    }

    //后序遍历

    public static void postOrder(Node root) {
        if (root != null) {
            root.postOrder();
        } else {
            System.out.println("空数 ，无数据。。。");
        }
    }


}
